#include<iostream>
#include<vector>
#include<string>
using namespace std;

class TreeNode{
public:
    int val;
    TreeNode *left;
    TreeNode *right;
};

//2331.计算布尔二叉树的值
bool evaluateTree(TreeNode* root){
    if(root->left==nullptr&&root->right==nullptr){
        return root->val;
    }

    //递归计算左右子树的布尔值
    bool left = evaluateTree(root->left);
    bool right = evaluateTree(root->right);

    bool ret;

    if(root->val==2){
        ret = left | right;
    }
    if(root->val==3){
        ret = left & right;
    }
    return ret;
}

//LCR.049.求根节点到叶子结点的值
//函数名，用到的参数有两个，一个是当前节点，另一个是当前节点的父节点传过来的值
//返回当前节点的左右子树的值之和
int dfs(TreeNode* root,int parentval){
    if(root==nullptr){
        return 0;
    }

    parentval = parentval * 10 + root->val;
    
    if(root->left==nullptr&&root->right==nullptr){
        return parentval;
    }

    //递归计算左右子树的值之和
    int left = dfs(root->left, parentval);
    int right = dfs(root->right, parentval);
    return left + right;
}
int sumNumbers(TreeNode* root){
    return dfs(root, 0);
}


//LCR.047.二叉树剪枝
TreeNode* pruneTree(TreeNode* root){
    //在处理当前节点时，需要先找到左右子树的情况，才能判断当前节点是否需要剪枝
    //因此类似于二叉树的后序遍历

    //结束条件，当遇到空节点时，直接返回空节点
    if(root==nullptr){
        return nullptr;
    }

    //递归左右子树
    root->left=pruneTree(root->left);
    root->right = pruneTree(root->right);

    //判断当前节点是否需要剪枝
    if(root->left==nullptr&&root->right==nullptr&&root->val==0){
        //delete root;
        root = nullptr;
    }
    return root;
}

//98.验证二叉搜索树
//刚开始的思路是类似于二叉树的后序遍历，先判断左右子树是否符合，然后再判断当前节点是否符合，然后将三者的真值&，返回
//但是这里有个错误点，就是出现下面这种情况就会判断出错
//           20
//       10      30
//     7   15   19  38
//因此本道题的正确思路时借助二叉搜索树中序遍历的性质，中序遍历时一个递增的有序序列
long prev = LONG_MIN;
bool isValidBST(TreeNode* root){
    if(root==nullptr){
        return true;
    }

    bool left = isValidBST(root->left);
    //剪枝，如果左子树返回的是false，可以直接结束当前节点的判断和右子树的递归，直接返回false
    if(left==false){
        return false;
    }

    bool ret = false;
    if(root->val>prev){
        ret = true;
    }
    //剪枝，如果当前节点判断结果是false,也可以直接结束右子树的递归，直接返回false
    if(ret==false){
        return false;
    }

    prev = root->val;
    bool right = isValidBST(root->right);

    return left & right & ret;
}

//230.二叉搜索树中第K小的元素
//借助两个全局变量，一个用来统计次数第几个，一个用来返回最终结果
int count;
int ret;
int dfs(TreeNode* root){
    //中序遍历加剪枝优化
    if(root==nullptr){
        return ret;
    }

    ret = dfs(root->left);

    count--;
    if(count==0){
        ret = root->val;
        return ret;
    }

    ret = dfs(root->right);

    return ret;
}
int kthSmallest(TreeNode* root, int k){
    count=k;
    ret = 0;
    return dfs(root);
}

//257.二叉树的所有路径
void dfs1(TreeNode *root, vector<string> &ret, string path){
    if(root==nullptr){
        return;
    }

    if(root->left==nullptr&&root->right==nullptr){
        path += to_string(root->val);
        ret.push_back(path);
    }
    path += to_string(root->val);
    path += "->";

    dfs1(root->left, ret, path);
    dfs1(root->right, ret, path);
}

vector<string> binaryTreePaths(TreeNode* root){
    vector<string> ret;
    string path;

    //这里直接通过函数的性质增加一个参数变量字符串path,用来“恢复现场”
    dfs1(root,ret,path);

    return ret;
}

int main(){

    return 0;
}